In the area of data processors, a pipeline system is a system having computational and combinational capabilities divided into several sequential stages, each of which may be active with an independent set of data at the same instant of time. Data is viewed as flowing from one pipeline stage where it is acted upon or processed to another for further action or processing. To increase pipeline throughput new data is fed to the first stages thereof while old data is still being acted upon in the latter stages. Maximum throughput wherein all stages are busy all of the time is a goal seldom achieved in any pipeline system over an extended period of time.
Often the pipeline system is microprogrammable wherein each stage thereof responds to microinstructions. For example, an arithmetic element stage may respond to microinstructions requesting arithmetic operations such as add, divide, multiply, etc., and to other control instructions requesting Boolean operations to be performed. A simple memory stage may be requested by a control microinstruction to read from a particular address, and to output to a particular bus, register or stage, or to store data in a particular address. In microprogrammable pipeline system design striving to maximize throughput, the task of providing the proper control microinstructions to the various stages in correct sequential order becomes quite complex, see "The Microprogramming of Pipelined Processors", P. M. Kogge, "THE FOURTH ANNUAL SYMPOSIUM ON COMPUTER ARCHITECTURE", pp 63-69.
Additional problems in microprogrammably controlling pipeline stages occur when feedback flow within and among the stages is allowed. Feedback flow allows data to be fully processed in one complete flow through the pipeline and eliminates the need for duplicate stages in the pipeline, which stages may be required by only a small percentage of the data flowing therethrough.
A set of microinstructions controlling the flow of an individual set of data through the pipeline is a template. The overall flow of data through the pipeline then becomes controlled by a sequence of templates. The templates must be stored and fed to the pipeline stages in a manner to avoid collisions. This becomes particularly important and increasingly difficult in situations involving pipeline feedback.
Thus, the controlling system for initiating and sequencing templates must be capable of initiating templates sequentially in a manner to produce high pipeline throughput without collisions. A prior microprogrammed pipeline controlling system has been proposed using shift registers, see E. S. Davidson et al, "Effective Control for Pipelined Computers", Proc. Compcon, Spring 1975, pp. 181-184. However, such a shift register controlling scheme becomes increasingly expensive for multiple template pipelined systems and the addition of new templates requires hardwire logic modifications. in the template control system design.
It is therefore an object of the invention to provide an efficient template initiation and sequencing control method and apparatus for a microprogrammed pipelined data processing system.
It is another object of the present invention to provide an improved template control system that can accept new templates without requiring hardwire modifications.